题面

解题思路

两遍Dijkstra染色

说几句闲话

最近几天状态不是很好，想题目也没什么思路，深深地明白自己的弱小

分析

  • $O(n\log^2n)$ 算法

    由于距离最近的点之间，二进制肯定有一位不同，因此我们可以把点按照二进制位为 $1/0$ 分成两组，然后做 $\log k$ 次多源多汇最短路即可，这样的时间复杂度为 $O(n\log^2n)$

  • $O(n\log n)$ 算法

    个人认为这种算法前面的更加好想，但是没有上者来的妙，这种算法的思路是，枚举最短路经过的点，那么我们需要预处理离这条边两端最近的点，这个用两遍 $Dijkstra$，一遍建正边，一遍建反边，然后记录离每个点最近的感兴趣的城市用于之后判断即可

Code

$O(n\log^2n)\ version:$

#include<bits/stdc++.h>
#define getchar() *(pos++)
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define M 500003
#define N 100003
using namespace std;
char bf[1<<25],*pos=bf;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
struct Edge{
    int to,nxt,cost;
    Edge(int a,int b,int c):to(a),nxt(b),cost(c){}
    Edge(){}
}b[M];
struct node{
    int p;LL cost;
    node(int a,rll b):p(a),cost(b){}
    node(){}
    inline bool operator< (const node x) const{
        return cost>x.cost;
    }
};
int head[N],n,m,T,t,K,a[N],num,E[N];
LL d[N],ans;bool vis[N];
inline void add(rint x,rint y,rint cost) {
    b[++t]=Edge(y,head[x],cost),head[x]=t;
}
inline void DS() {
    rint i,to,cur;rll cost;
    priority_queue<node>p;
    memset(vis,0,n+1),
    memset(d,inf,(n+1)<<3);
    for(i=1;i<=K;i++) if(E[a[i]]-1) p.push(node(a[i],0)),d[a[i]]=0;
    while(!p.empty()) {
        cur=p.top().p,p.pop();
        if(E[cur]==1) return cmin(ans,d[cur]),void();
        if(vis[cur]) continue;vis[cur]=1;
        for(i=head[cur];i;i=b[i].nxt) {
            to=b[i].to,cost=b[i].cost+d[cur];
            if(d[to]>cost) d[to]=cost,p.push(node(to,cost));
        }
    }
}
inline void DE() {
    rint i,to,cur;rll cost;
    priority_queue<node>p;
    memset(vis,0,n+1),
    memset(d,inf,(n+2)<<3);
    for(i=1;i<=K;i++) if(E[a[i]]==1) p.push(node(a[i],0)),d[a[i]]=0;
    while(!p.empty()) {
        cur=p.top().p,p.pop();
        if(E[cur]==2) return cmin(ans,d[cur]),void();
        if(vis[cur]) continue;vis[cur]=1;
        for(i=head[cur];i;i=b[i].nxt) {
            to=b[i].to,cost=b[i].cost+d[cur];
            if(d[to]>cost) d[to]=cost,p.push(node(to,cost));
        }
    }
}
int main() {
    bf[fread(bf,1,1<<25,stdin)]='\0';
    rint i,x,y,cost,c;T=read();
    while(T--) {
        n=read(),m=read(),K=read(),
        t=0,ans=1e16,memset(head,0,(n+1)<<2);
        for(i=1;i<=m;i++) {
            x=read(),y=read(),cost=read();
            if(x==y) continue;
            add(x,y,cost);
        }
        for(i=1;i<=K;i++) a[i]=read();
        for(c=1;c<=K;c<<=1) {//每位做一个多源多汇最短路
            num=K;
            for(i=1;i<=K;i++)
                if(i&c) E[a[i]]=1,--num;
                else E[a[i]]=2;
            if(0<num&&num<K) DS(),DE();
        }memset(E,0,(n+1)<<2);
        printf("%lld\n",ans);
    }
}

$O(n\log n)\ version:$

#include<bits/stdc++.h>
#define getchar() *(pos++)
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x3f3f3f3f
#define M 500003
#define N 100003
using namespace std;
char bf[1<<25],*pos=bf;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
struct RealEdge{
    int x,y,cost;
}E[M];
struct Edge{
    int to,nxt,cost;
    Edge(int a,int b,int c):to(a),nxt(b),cost(c){}
    Edge(){}
}b[M];
struct node{
    int p;LL cost;
    node(int a,rll b):p(a),cost(b){}
    inline bool operator< (const node x) const{
        return cost>x.cost;
    }
};
int head[N],T,t,n,m,k,res,a[N],bl[2][N];
LL d[2][N],ans;bool vis[N];
inline void add(rint x,rint y,rint cost)  {
    b[++t]=Edge(y,head[x],cost),head[x]=t;
}
inline void Dijkstra(rll *d,rint *bl) {
    rint i,to,c;rll cost;
    priority_queue<node>p;
    memset(d,inf,(n+1)<<3),
    memset(vis,0,n+1);
    for(i=1;i<=k;i++) p.push(node(a[i],0)),d[a[i]]=0,bl[a[i]]=a[i];
    while(!p.empty()) {
        c=p.top().p,p.pop();
        if(vis[c]) continue;vis[c]=1;
        for(i=head[c];i;i=b[i].nxt) {
            to=b[i].to,cost=d[c]+b[i].cost;
            if(d[to]>cost)//染色，即记录有哪个感兴趣的城市更新而来
                d[to]=cost,bl[to]=bl[c],p.push(node(to,cost));
        }
    }
}
int main()
{
    bf[fread(bf,1,1<<25,stdin)]='\0';
    rint i,x,y,cost;T=read();
    while(T--) {
        n=read(),m=read(),k=read(),ans=1e16,
        res=t=0,memset(head,0,(n+1)<<2);
        for(i=1;i<=m;i++) {
            x=read(),y=read(),cost=read();
            if(x==y) continue;add(x,y,cost);
            E[++res].x=x,E[res].y=y,E[res].cost=cost;
        }
        for(i=1;i<=k;i++) a[i]=read();
        Dijkstra(d[0],bl[0]);//跑正向多源最短路
        memset(head,0,(n+1)<<2),t=0;
        for(i=1;i<=res;i++)    add(E[i].y,E[i].x,E[i].cost);
        Dijkstra(d[1],bl[1]);//反向
        for(i=1;i<=res;i++) {
            x=E[i].x,y=E[i].y,cost=E[i].cost;//最后判断一下即可
            if(bl[0][x]!=bl[1][y]) cmin(ans,d[0][x]+d[1][y]+cost);
        }printf("%lld\n",ans);
    }
    return 0;
}

devil.